//////////////////////////////////////////////////////
// 程序名称：用逐边裁剪法实现多边形裁剪
// 功 能：处理退化边
// 编译环境：Visual Studio 2017，EasyX_20190219(beta)
// 作 者：xyqlx<mxxyqlx@qq.com>
// 最后修改：2019-3-31
#include <conio.h>
#include <graphics.h>
#include <cmath>
#include <list>
#include <utility>

COLORREF currentColor = RED;

void MPLline(int x1, int y1, int x2, int y2, COLORREF color)
{
	int a, b, d1, d2, d, x, y;
	if (x1 > x2)
	{
		x1 ^= x2;
		x2 ^= x1;
		x1 ^= x2;
		y1 ^= y2;
		y2 ^= y1;
		y1 ^= y2;
	}
	x = x2 - x1;
	y = y2 - y1;
	if (y >= x)
	{
		a = x1 - x2;
		b = y2 - y1;
		d = 2 * a + b;
		d1 = 2 * (a + b);
		d2 = 2 * a;
		x = x1;
		y = y1;
		putpixel(x, y, color);
		while (y < y2)
		{
			if (d < 0)
			{
				x++;
				y++;
				d += d1;
			}
			else
			{
				y++;
				d += d2;
			}
			putpixel(x, y, color);
		}
	}
	else if (y <= x && y >= 0)
	{
		a = y1 - y2;
		b = x2 - x1;
		d = 2 * a + b;
		d1 = 2 * (a + b);
		d2 = 2 * a;
		x = x1;
		y = y1;
		putpixel(x, y, color);
		while (x < x2)
		{
			if (d < 0)
			{
				x++;
				y++;
				d += d1;
			}
			else
			{
				x++;
				d += d2;
			}
			putpixel(x, y, color);
		}
	}
	else if (y >= -x)
	{
		a = y2 - y1;
		b = x2 - x1;
		d = 2 * a + b;
		d1 = 2 * (a + b);
		d2 = 2 * a;
		x = x1;
		y = y1;
		putpixel(x, y, color);
		while (x < x2)
		{
			if (d < 0)
			{
				x++;
				y--;
				d += d1;
			}
			else
			{
				x++;
				d += d2;
			}
			putpixel(x, y, color);
		}
	}
	else
	{
		a = x1 - x2;
		b = y1 - y2;
		d = 2 * a + b;
		d1 = 2 * (a + b);
		d2 = 2 * a;
		x = x1;
		y = y1;
		putpixel(x, y, color);
		while (y > y2)
		{
			if (d < 0)
			{
				x++;
				y--;
				d += d1;
			}
			else
			{
				y--;
				d += d2;
			}
			putpixel(x, y, color);
		}
	}
}

class Shape
{
  public:
	Shape(int n) : stateNum(n) {}
	virtual void Redraw() = 0;
	int stateNum;
	virtual void State(int &state, int x, int y) = 0;
	virtual ~Shape(){};
};

class Line : public Shape
{
  public:
	int x1, y1, x2, y2;
	COLORREF lineColor;
	Line() : Shape(4) {}
	Line(int x1, int y1, int x2, int y2, COLORREF lineColor) : Shape(4), x1(x1), y1(y1), x2(x2), y2(y2), lineColor(lineColor) {}
	virtual void Redraw()
	{
		MPLline(x1, y1, x2, y2, lineColor);
	}
	virtual void State(int &state, int x, int y)
	{
		switch (state)
		{
		case 1:
			x1 = x;
			y1 = y;
			break;
		case 2:
			x2 = x;
			y2 = y;
			lineColor = currentColor;
		case 3:
			MPLline(x1, y1, x2, y2, lineColor);
			break;
		}
	}
	virtual ~Line() {}
};

class SRectangle : public Shape
{
  public:
	int left, right, bottom, top;
	COLORREF lineColor;
	SRectangle() : Shape(4) {}
	SRectangle(int left, int right, int bottom, int top, COLORREF lineColor) : Shape(4), left(left), right(right), bottom(bottom), top(top), lineColor(lineColor) {}
	virtual void Redraw()
	{
		MPLline(left, top, right, top, lineColor);
		MPLline(left, top, left, bottom, lineColor);
		MPLline(left, bottom, right, bottom, lineColor);
		MPLline(right, bottom, right, top, lineColor);
	}
	virtual void State(int &state, int x, int y)
	{
		switch (state)
		{
		case 1:
			left = x;
			top = y;
			break;
		case 2:
			right = x;
			bottom = y;
			lineColor = currentColor;
			Redraw();
			break;
		case 3:
			if (left > right)
			{
				int t = left;
				left = right;
				right = t;
			}
			if (bottom > top)
			{
				int t = bottom;
				bottom = top;
				top = t;
			}
			Redraw();
			break;
		}
	}
	virtual ~SRectangle() {}
};

class SPolygon : public Shape
{
  public:
	std::list<std::pair<int, int>> vertices;
	COLORREF lineColor;
	SPolygon() : Shape(4) {}
	SPolygon(std::list<std::pair<int, int>> vertices, COLORREF lineColor) : Shape(4), vertices(vertices), lineColor(lineColor) {}
	SPolygon(int *points, int length, COLORREF lineColor) : Shape(4), lineColor(lineColor)
	{
		for (int i = 0; i < length / 2; ++i)
		{
			vertices.push_back(std::make_pair(points[2 * i], points[2 * i + 1]));
		}
		vertices.push_back(std::make_pair(points[0], points[1]));
	}
	virtual void Redraw()
	{
		std::list<std::pair<int, int>>::iterator it = vertices.begin(), pit;
		for (pit = it, ++it; it != vertices.end(); ++it)
		{
			MPLline(pit->first, pit->second, it->first, it->second, lineColor);
			pit = it;
		}
	}
	virtual void State(int &state, int x, int y)
	{
		switch (state)
		{
		case 1:
			vertices.push_back(std::make_pair(x, y));
			vertices.push_back(std::make_pair(x, y));
			break;
		case 2:
			vertices.back().first = x;
			vertices.back().second = y;
			lineColor = currentColor;
			Redraw();
			break;
		case 3:
			vertices.push_back(std::make_pair(x, y));
			if (abs(x - vertices.front().first) < 5 && abs(y - vertices.front().second) < 5)
			{
				vertices.pop_back();
				vertices.back().first = vertices.front().first;
				vertices.back().second = vertices.front().second;
			}
			else
				state -= 2;
			Redraw();
			break;
		}
	}
	virtual ~SPolygon() {}
};

//其实这里没有判断溢出的机制
Shape *shapes[10010];
Shape *currentShape;
int shapeIndex = 0;

//使用缓冲技术，减少因图形数量增加时出现的大量Redraw消耗
IMAGE img(640, 480);

void Refresh()
{
	SetWorkingImage();
	putimage(0, 0, &img, SRCCOPY);
}

//有生之年第一次在示例之外用到工厂函数（
class ShapeFactory
{
  public:
	//其实用枚举更好
	static int maxID;
	int shapeID = 1;
	void changeShape()
	{
		if (++shapeID > maxID)
		{
			shapeID = 1;
		}
	}
	Shape *createShape()
	{
		switch (shapeID)
		{
		case 1:
			return new Line();
		case 2:
			return new SRectangle();
		case 3:
			return new SPolygon();
		default:
			return new Line();
		}
	}
};
int ShapeFactory::maxID = 3;

//左裁剪框
SRectangle lclipRect(5, 140, 74, 149, GREEN);
//右裁剪框
SRectangle rclipRect(325, 460, 74, 149, GREEN);

//初始化画布和屏幕(现在已经是用来全部重绘的函数了)
void Init()
{
	//填充背景为白色
	SetWorkingImage(&img);
	setbkcolor(WHITE);
	cleardevice();

	for (int i = 0; i < shapeIndex; ++i)
	{
		if (shapes[i])
			shapes[i]->Redraw();
	}
	SetWorkingImage();
	Refresh();
}

//清理函数（虽然似乎不会执行）
void Clear()
{
	for (int i = 0; i < shapeIndex; ++i)
	{
		delete shapes[i];
	}
}

bool L_B_LineClip(Line &line, const SRectangle &rect);
bool S_H_PolygonClip(SPolygon &polygon, const SRectangle &rect);
int SplitPolygon(SPolygon &polygon, const SRectangle &rect, std::list<SPolygon> &res);

void CopyClipLine(const Line &line)
{
	Line *currentLine = new Line(line.x1 + 320, line.y1, line.x2 + 320, line.y2, line.lineColor);
	if (L_B_LineClip(*currentLine, rclipRect))
	{
		shapes[shapeIndex++] = currentLine;
		SetWorkingImage(&img);
		currentLine->Redraw();
		SetWorkingImage();
		currentLine->Redraw();
	}
	else
	{
		delete currentLine;
		currentLine = NULL;
	}
}

void CopyClipPolygon(const SPolygon &polygon)
{
	std::list<std::pair<int, int>> vlist = polygon.vertices;
	for (std::list<std::pair<int, int>>::iterator it = vlist.begin(); it != vlist.end(); ++it)
	{
		it->first += 320;
	}
	SPolygon *currentPolygon = new SPolygon(vlist, polygon.lineColor);

	if (S_H_PolygonClip(*currentPolygon, rclipRect))
	{
		std::list<SPolygon> plist;
		SplitPolygon(*currentPolygon, rclipRect, plist);
		for (auto i : plist)
		{
			SPolygon *tempPolygon = new SPolygon(i);
			shapes[shapeIndex++] = tempPolygon;
			SetWorkingImage(&img);
			i.Redraw();
			//currentPolygon->Redraw();
			SetWorkingImage();
			i.Redraw();
			//currentPolygon->Redraw();
		}
	}
	else
	{
		delete currentPolygon;
		currentPolygon = NULL;
	}
}

bool isDisplay()
{
	HWND hWnd = GetHWnd();
	MessageBox(hWnd, TEXT("左：绘图窗口，右：展示窗口"), TEXT("窗口介绍"), MB_ICONINFORMATION);
	MessageBox(hWnd, TEXT("左键点选多边形的顶点，在起点5像素距离内画点会闭合。右键点选裁剪框的两个顶点。"), TEXT("操作介绍"), MB_ICONINFORMATION);
	return MessageBox(hWnd, TEXT("是否运行展示"), TEXT("功能选择"), MB_YESNO | MB_ICONQUESTION) == IDYES;
}

void Display()
{
	int data[18] = {110, 84, 160, 94, 90, 169, 90, 94, 70, 90, 50, 189, 165, 189, 175, 89, 163, 54};
	SPolygon *sample = new SPolygon(data, 18, RED);
	SetWorkingImage(&img);
	sample->Redraw();
	CopyClipPolygon(*sample);
	shapes[shapeIndex++] = sample;
	Refresh();
}

//主消息循环
void MessageLoop()
{
	MOUSEMSG msg;
	HWND hWnd = GetHWnd();
	char titleBuffer[100];
	WCHAR wTitleBuffer[100];
	size_t len;
	currentShape = new SPolygon;
	int cnt = 0;
	ShapeFactory shapeFactory;
	shapeFactory.shapeID = 3;

	//缺少说明，仅仅用于调试
	while (1)
	{
		msg = GetMouseMsg();
		switch (msg.uMsg)
		{
		case WM_MOUSEMOVE:
			if (cnt)
			{
				Refresh();
				if (currentShape)
					currentShape->State(cnt, msg.x, msg.y);
				else
					lclipRect.State(cnt, msg.x, msg.y);
			}
			break;
		case WM_LBUTTONDOWN:
			Refresh();
			if(!currentShape){
				currentColor = RED;
				cnt = 0;
				currentShape = shapeFactory.createShape();
			}
				
			currentShape->State(++cnt, msg.x, msg.y);
			if (++cnt >= currentShape->stateNum)
			{
				shapes[shapeIndex++] = currentShape;
				//这里暂时这样写
				Line *currentLine = dynamic_cast<Line *>(currentShape);
				if (currentLine)
				{
					CopyClipLine(*currentLine);
				}
				else
				{
					SPolygon *currentPolygon = dynamic_cast<SPolygon *>(currentShape);
					if (currentPolygon)
						CopyClipPolygon(*currentPolygon);
				}
				SetWorkingImage(&img);
				currentShape->Redraw();
				SetWorkingImage();
				currentShape = shapeFactory.createShape();
				cnt = 0;
			}
			Refresh();
			//添加使用空间消息
			sprintf_s(titleBuffer, "Space %d/%d used", shapeIndex, 10000);
			len = strlen(titleBuffer);
			MultiByteToWideChar( 0,0, titleBuffer, -1 , wTitleBuffer, 100 ); 
			SetWindowText(hWnd, wTitleBuffer);
			break;
		case WM_RBUTTONDOWN:
			if (currentShape)
			{
				currentColor = GREEN;
				cnt = 0;
				delete currentShape;
				currentShape = NULL;
			}
			Refresh();
			lclipRect.State(++cnt, msg.x, msg.y);
			if (++cnt >= lclipRect.stateNum)
			{
				//重绘并裁剪
				rclipRect = lclipRect;
				rclipRect.left += 320;
				rclipRect.right += 320;
				int currentShapeIndex = shapeIndex;
				for (int i = 0; i < currentShapeIndex; ++i)
				{
					if (shapes[i])
					{
						Line *line = dynamic_cast<Line *>(shapes[i]);
						if (line)
						{
							if (line->x1 > 320 || line->x2 > 320)
							{
								delete shapes[i];
								shapes[i] = 0;
							}
							else
							{
								CopyClipLine(*line);
							}
						}
						else
						{
							SPolygon *polygon = dynamic_cast<SPolygon *>(shapes[i]);
							if (polygon)
							{
								if (!polygon->vertices.empty() && polygon->vertices.front().first > 320)
								{
									delete shapes[i];
									shapes[i] = 0;
								}
								else
								{
									CopyClipPolygon(*polygon);
								}
							}
						}
					}
				}
				Init();
				currentShape = shapeFactory.createShape();
				currentColor = RED;
				cnt = 0;
			}
			Refresh();
			break;
		}
	}
}

int main()
{
	// 创建绘图窗口，大小为 640x480 像素
	initgraph(640, 480);
	//初始化
	//绘制分割线
	shapes[shapeIndex++] = new Line(320, 0, 320, 480, BLACK);
	//绘制裁剪框
	shapes[shapeIndex++] = &lclipRect;
	Init();
	//展示
	if (isDisplay())
		Display();
	//开始绘制
	MessageLoop();
	//结束绘制
	_getch();	 // 按任意键继续
	closegraph(); // 关闭绘图窗口
	Clear();
	return 0;
}

//以下是主要内容
bool S_H_PolygonClip(SPolygon &polygon, const SRectangle &rect)
{
	std::list<std::pair<int, int>> newVertices;
	std::list<std::pair<int, int>>::iterator it, pit;

	it = polygon.vertices.begin();
	if (it->first <= rect.right)
		newVertices.push_back(*it);
	for (pit = it, ++it; it != polygon.vertices.end(); ++it)
	{
		if (pit->first <= rect.right && it->first > rect.right)
			newVertices.push_back(std::make_pair(rect.right, (it->second - pit->second) * (rect.right - it->first) / (it->first - pit->first) + it->second));
		else if (it->first <= rect.right)
		{
			if (pit->first > rect.right)
				newVertices.push_back(std::make_pair(rect.right, (it->second - pit->second) * (rect.right - it->first) / (it->first - pit->first) + it->second));
			newVertices.push_back(*it);
		}
		pit = it;
	}
	if (newVertices.empty())
		return 0;
	if (newVertices.back() != newVertices.front())
		newVertices.push_back(newVertices.front());
	polygon.vertices = newVertices;

	newVertices.clear();
	it = polygon.vertices.begin();
	if (it->first >= rect.left)
		newVertices.push_back(*it);
	for (pit = it, ++it; it != polygon.vertices.end(); ++it)
	{
		if (pit->first >= rect.left && it->first < rect.left)
			newVertices.push_back(std::make_pair(rect.left, (it->second - pit->second) * (rect.left - it->first) / (it->first - pit->first) + it->second));
		else if (it->first >= rect.left)
		{
			if (pit->first < rect.left)
				newVertices.push_back(std::make_pair(rect.left, (it->second - pit->second) * (rect.left - it->first) / (it->first - pit->first) + it->second));
			newVertices.push_back(*it);
		}
		pit = it;
	}
	if (newVertices.empty())
		return 0;
	if (newVertices.back() != newVertices.front())
		newVertices.push_back(newVertices.front());
	polygon.vertices = newVertices;

	newVertices.clear();
	it = polygon.vertices.begin();
	if (it->second <= rect.top)
		newVertices.push_back(*it);
	for (pit = it, ++it; it != polygon.vertices.end(); ++it)
	{
		if (pit->second <= rect.top && it->second > rect.top)
			newVertices.push_back(std::make_pair((it->first - pit->first) * (rect.top - it->second) / (it->second - pit->second) + it->first, rect.top));
		else if (it->second <= rect.top)
		{
			if (pit->second > rect.top)
				newVertices.push_back(std::make_pair((it->first - pit->first) * (rect.top - it->second) / (it->second - pit->second) + it->first, rect.top));
			newVertices.push_back(*it);
		}
		pit = it;
	}
	if (newVertices.empty())
		return 0;
	if (newVertices.back() != newVertices.front())
		newVertices.push_back(newVertices.front());
	polygon.vertices = newVertices;

	newVertices.clear();
	it = polygon.vertices.begin();
	if (it->second >= rect.bottom)
		newVertices.push_back(*it);
	for (pit = it, ++it; it != polygon.vertices.end(); ++it)
	{
		if (pit->second >= rect.bottom && it->second < rect.bottom)
			newVertices.push_back(std::make_pair((it->first - pit->first) * (rect.bottom - it->second) / (it->second - pit->second) + it->first, rect.bottom));
		else if (it->second >= rect.bottom)
		{
			if (pit->second < rect.bottom)
				newVertices.push_back(std::make_pair((it->first - pit->first) * (rect.bottom - it->second) / (it->second - pit->second) + it->first, rect.bottom));
			newVertices.push_back(*it);
		}
		pit = it;
	}
	if (newVertices.empty())
		return 0;
	if (newVertices.back() != newVertices.front())
		newVertices.push_back(newVertices.front());
	polygon.vertices = newVertices;

	return 1;
}

#define LEFT 1
#define RIGHT 2
#define BOTTOM 4
#define TOP 8

int encode(int x, int y, const SRectangle &rect)
{
	int c = 0;
	if (x == rect.left)
		c = c | LEFT;
	else if (x == rect.right)
		c = c | RIGHT;
	if (y == rect.bottom)
		c = c | BOTTOM;
	else if (y == rect.top)
		c = c | TOP;
	return c;
}

int SplitPolygon(SPolygon &polygon, const SRectangle &rect, std::list<SPolygon> &res)
{
	std::list<std::pair<int, int>> newVertices;
	std::list<std::pair<int, int>>::iterator sit, it, nit;
	int cnt = 1;

	sit = polygon.vertices.begin();
	for (++sit; sit != polygon.vertices.end(); ++sit)
	{
		int scode = encode(sit->first, sit->second, rect);
		if (scode == 0)
			continue;
		newVertices.clear();
		newVertices.push_back(*sit);
		it = sit;
		++it;
		if (it != polygon.vertices.end())
		{
			for (;; ++it)
			{
				nit = it;
				++nit;
				if (nit == polygon.vertices.end())
					break;
				newVertices.push_back(*it);
				int code = encode(it->first, it->second, rect);
				int rcode = scode & code;
				if (rcode)
				{
					if (rcode & (BOTTOM | TOP))
					{
						if (((sit->first < it->first) ^ (sit->first < nit->first)) || sit->first == nit->first)
						{
							newVertices.push_back(*sit);
							res.push_back(SPolygon(newVertices, polygon.lineColor));
							nit = polygon.vertices.insert(nit, *sit);
							sit = polygon.vertices.erase(sit, nit);
							++cnt;
							break;
						}
					}
					else
					{
						if (((sit->second < it->second) ^ (sit->second < nit->second)) || sit->second == nit->second)
						{
							newVertices.push_back(*sit);
							res.push_back(SPolygon(newVertices, polygon.lineColor));
							nit = polygon.vertices.insert(nit, *sit);
							sit = polygon.vertices.erase(sit, nit);
							++cnt;
							break;
						}
					}
				}
			}
		}
	}
	res.push_back(SPolygon(polygon.vertices, polygon.lineColor));
	if (cnt != 1)
	{
		std::list<SPolygon>::iterator it = res.end();
		--it;
		for (int i = 0; i < cnt; ++i)
		{
			SPolygon sp(*it);
			it = res.erase(it);
			if (it != res.begin())
				--it;

			int mcode = 15;
			for (std::list<std::pair<int, int>>::iterator pit = sp.vertices.begin(); pit != sp.vertices.end(); ++pit)
			{
				mcode &= encode(pit->first, pit->second, rect);
			}

			if (!mcode)
				SplitPolygon(sp, rect, res);
		}
	}
	return cnt;
}

bool L_B_LineClip(Line &line, const SRectangle &rect)
{
	int p1 = line.x1 - line.x2;
	int q1 = line.x1 - rect.left;
	int q2 = rect.right - line.x1;
	int p3 = line.y1 - line.y2;
	int q3 = line.y1 - rect.bottom;
	int q4 = rect.top - line.y1;
	double umax = 0, umin = 1;
	if (!p1)
	{
		if (q1 < 0 || q2 < 0)
			return 0;
		if (p3 < 0)
		{
			double u3 = double(q3) / p3, u4 = double(q4) / -p3;
			if (u3 > umax)
				umax = u3;
			if (u4 < umin)
				umin = u4;
		}
		else
		{
			double u3 = double(q3) / p3, u4 = double(q4) / -p3;
			if (u4 > umax)
				umax = u4;
			if (u3 < umin)
				umin = u3;
		}
	}
	else if (!p3)
	{
		if (q3 < 0 || q4 < 0)
			return 0;
		if (p1 < 0)
		{
			double u1 = double(q1) / p1, u2 = double(q2) / -p1;
			if (u1 > umax)
				umax = u1;
			if (u2 < umin)
				umin = u2;
		}
		else
		{
			double u1 = double(q1) / p1, u2 = double(q2) / -p1;
			if (u2 > umax)
				umax = u2;
			if (u1 < umin)
				umin = u1;
		}
	}
	else
	{
		if (p3 < 0)
		{
			double u3 = double(q3) / p3, u4 = double(q4) / -p3;
			if (u3 > umax)
				umax = u3;
			if (u4 < umin)
				umin = u4;
		}
		else
		{
			double u3 = double(q3) / p3, u4 = double(q4) / -p3;
			if (u4 > umax)
				umax = u4;
			if (u3 < umin)
				umin = u3;
		}
		if (p1 < 0)
		{
			double u1 = double(q1) / p1, u2 = double(q2) / -p1;
			if (u1 > umax)
				umax = u1;
			if (u2 < umin)
				umin = u2;
		}
		else
		{
			double u1 = double(q1) / p1, u2 = double(q2) / -p1;
			if (u2 > umax)
				umax = u2;
			if (u1 < umin)
				umin = u1;
		}
	}
	if (umax > umin)
		return 0;
	int x1 = line.x1 + umax * (line.x2 - line.x1);
	int y1 = line.y1 + umax * (line.y2 - line.y1);
	line.x2 = line.x1 + umin * (line.x2 - line.x1);
	line.y2 = line.y1 + umin * (line.y2 - line.y1);
	line.x1 = x1;
	line.y1 = y1;
	return 1;
}